Qu'est-ce que théorème des restes chinois ?

Le théorème des restes chinois est une méthode de théorie des nombres qui permet de trouver la solution d'un système d'équations modulaires. Plus précisément, il permet de trouver un nombre entier qui est congru à différents nombres modulo différents modèles.

Le théorème énonce que si l'on dispose d'un système d'équations de la forme : x ≡ a1 (mod. n1) x ≡ a2 (mod. n2) ... x ≡ ak (mod. nk)

avec n1, n2, ..., nk des nombres premiers deux à deux distincts, alors il existe un unique entier x qui satisfait à toutes les équations et qui est congru à a1 modulo n1, à a2 modulo n2, ..., et à ak modulo nk.

La formule générale qui permet de calculer x est : x ≡ (∑(i = 1 à k) aiMiMi') (mod m)

Où :

• Mi est l'inverse modulaire de ni dans l'anneau Z des entiers relatifs ;
• Mi' est l'inverse modulaire de Mi modulo ni ;
• m est le produit de tous les ni ;
• et le symbole ≡ signifie « congruent à ».

Le théorème des restes chinois est très utilisé en cryptographie et dans les codes correcteurs d'erreurs. Il permet également de résoudre de nombreux problèmes en mathématiques, en informatique et en physique.